The fair division of indivisible goods has long been an important topic in economics and, more recently, computer science. We investigate the existence of envy-free allocations of indivisible goods, that is, allocations where each player values her own allocated set of goods at least as highly as any other player's allocated set of goods. Under additive valuations, we show that even when the number of goods is larger than the number of agents by a linear fraction, envy-free allocations are unlikely to exist. We then show that when the number of goods is larger by a logarithmic factor, such allocations exist with high probability. We support these results experimentally and show that the asymptotic behavior of the theory holds even when the number of goods and agents is quite small. We demonstrate that there is a sharp phase transition from nonexistence to existence of envy-free allocations, and that on average the computational problem is hardest at that transition.

For decades researchers have struggled with the problem of envy-free cake cutting: how to divide a divisible good between multiple agents so that each agent likes his own allocation best. Although an envy-free cake cutting protocol was ultimately devised, it is unbounded, in the sense that the number of operations can be arbitrarily large, depending on the preferences of the agents. We ask whether bounded protocols exist when the agents' preferences are restricted. Our main result is an envy-free cake cutting protocol for agents with piecewise linear valuations, which requires a number of operations that is polynomial in natural parameters of the given instance.

We consider the problem of selecting fair divisions of a heterogeneous divisible good among a set of agents. Recent work (Cohler et al., AAAI 2011) focused on designing algorithms for computing maxsum—social welfare maximizing—allocations under the fairness notion of envy-freeness. Maxsum allocations can also be found under alternative notions such as equitability. In this paper, we examine the properties of these allocations. In particular, We provide conditions for when maxsum envy-free or equitable allocations are Pareto optimal and give examples where fairness with Pareto optimality is not possible. We also prove that maxsum envy-free allocations have weakly greater welfare than maxsum equitable allocations when agents have structured valuations, and we derive an approximate version of this inequality for general valuations.

We consider the problem of fairly dividing a heterogeneous divisible good among agents with different preferences. Previous work has shown that envy-free allocations, i.e., where each agent prefers its own allocation to any other, may not be efficient, in the sense of maximizing the total value of the agents. Our goal is to pinpoint the most efficient allocations among all envy-free allocations. We provide tractable algorithms for doing so under different assumptions regarding the preferences of the agents.